import java.util.ArrayList;
import java.util.Scanner;

public class Main4 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
		int[] res=new int[N];

		for (int i = 0; i < N; i++) {
			ArrayList<Integer> arr = new ArrayList<>();
			for(int j=0;j<4;j++) {
				arr.add(sc.nextInt());
			}
			arrs.add(arr);
		}
		
		for(int i = 0; i < N; i++) {
			int A=arrs.get(i).get(0);
			int B=arrs.get(i).get(1);
			int C=arrs.get(i).get(2);
			int Q=arrs.get(i).get(3);
			
			boolean flag=false;
			
			while(Q%C==0) {
				if((Q-A)%B==0) {
					res[i]=1;
					flag=true;
					break;
				}
				Q=Q/C;
			}
			
			if(!flag) {
				if((Q-A)%B==0) {
					res[i]=1;
					flag=true;
				}
			}
			
			if(!flag) {
				res[i]=0;
			}
		}
		
		for(int i=0;i<N;i++) {
			System.out.println(res[i]);
		}
		
		return;
	}
}
